% Define document
\documentclass[11pt]{scrartcl}

% Import packages
\usepackage[dutch,english]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{listings}
\usepackage{parskip} % split paragraphs by vertical space
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{gensymb}
\usepackage{tabularx} % for multicolumns
\usepackage{polynom} % long devision

\usepackage{tikz} 
\usetikzlibrary{calc,intersections,through,backgrounds}


% Begin document
\begin{document}
\selectlanguage{dutch}


%Add title
\title{Oefeningen TAI: \\
Oefenzitting 6: Hamming codes en BCH-codes (Decodering met PGZ)}
\date{}
\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% About
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{About}
Uitwerking van oefenziting 6 van Toepassingen van Algebra in Informatica gedoceerd in de 3e Bachelor Informatica aan de KULeuven in 2012.

Latex code van dit document te vinden op:\\
SVN checkout: \texttt{https://oefenzittingen-tai.googlecode.com/svn/trunk/}\\
Google code: \texttt{https://code.google.com/p/oefenzittingen-tai/}

Credits: Peter Roelants
%TODO: put your name here

Te gebruiken op eigen risico!




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 1 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 1}
$(9,7)$ Hamming code over $GF(8)$\\
$\alpha$ primitief element van $GF(8)$, nulpunt van $x^3 + x + 1$\\
\begin{tabularx}{\textwidth}{XX}
$\alpha^0 = 1 = [100]$

$\alpha^1 = \alpha = [010]$

$\alpha^2 = \alpha^2 = [001]$

$\alpha^3 = 1 + \alpha = [110]$

&
$\alpha^4 = \alpha + \alpha^2 = [011]$

$\alpha^5 = 1 + \alpha + \alpha^2 = [111]$

$\alpha^6 = 1 + \alpha^2 = [101]$

$(\alpha^7 = 1 = [100])$

\end{tabularx}
Een generatormatrix en bijhorende pariteitsmatrix van de $(9,7)$ Hamming code over $GF(8)$ zijn:\\
\[
G =
\begin{bmatrix}
	\alpha^5 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
	\alpha^6 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
	1		 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
	\alpha	 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
	\alpha^2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
	\alpha^3 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
	\alpha^4 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}
\]

\[
H =
\begin{bmatrix}
	1 & 0 & 1 & \alpha	& \alpha^2	& \alpha^3	& \alpha^4 & \alpha^5	& \alpha^6 \\
	0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{bmatrix}
\]

(a) Hoeveel codewoorden zijn er in de code?

(b) Welke dimensies heeft de decoderingstabel?

(c) Welke dimensies heeft de syndroomtabel?

(d) Codeer een zelfgekozen informatiewoord.

(e) Bereken voor het onder (d) bekomen codewoord $c: cH^T$.

(f) Zet op het codewoord $c$ \'e\'en fout en bereken voor dit ontvangen woord $v$ het syndroom $s$.

(g) Hoe kan men, zonder gebruik te maken van de syndroomtabel uit $s$ en $v$ het correcte codewoord terugvinden.





\subsection*{oplossing 1.(a)}
Hamming codes: p.47 cursus.

Lengte informatiewoord = $k$ = 7.\\
Aantal verschillende elementen in $GF(8)$ = 8\\
$\Rightarrow$ er zijn $8^7$ geldige codewoorden.

(Codewoordlengte = $n$ = 9,  $\Rightarrow$ er zijn $8^9$ mogelijke ontvangen codewoorden)


\subsection*{oplossing 1.(b)}
Decoderingstabel: p.44 cursus.

Aantal kolommen = aantal geldige codewoorden = $8^7$ kolommen

Totaal aantal elementen = aantal mogelijke ontvangen codewoorden = $8^9$\\
$\Rightarrow$ Aantal rijen = \#aantal elementen/\#aantal kolommen = $8^9 / 8^7 = 8^2 = 64$ rijen



\subsection*{oplossing 1.(c)}
Syndroomtabel: p.46 cursus.

Syndroomtabel heeft 2 kolommen.

Syndroomtabel heeft hetzelfde aantal rijen als de decoderingstabel = $8^2 = 64$ rijen.\\
$\Rightarrow$ 64 syndromen. 



\subsection*{oplossing 1.(d)}
Coderen lineaire blokcode: p.40 cursus.

$i = 
\begin{bmatrix}
	1 & \alpha & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6
\end{bmatrix}
$

$c = i * G =
\begin{bmatrix}
	\alpha^5 + \alpha^7 + \alpha^2 + \alpha^4 + \alpha^6 + \alpha^8 + \alpha^{10} \\
	1 + \alpha + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 \\
	\alpha^2 \\
	\alpha^3 \\
	\alpha^4 \\
	\alpha^5 \\
	\alpha^6 \\
	1 \\
	\alpha
\end{bmatrix}^T
=
\begin{bmatrix}
	\alpha^5 + 1 + \alpha^2 + \alpha^4 + \alpha^6 + \alpha^1 + \alpha^3 \\
	1 + \alpha + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 \\
	\alpha^2 \\
	\alpha^3 \\
	\alpha^4 \\
	\alpha^5 \\
	\alpha^6 \\
	1 \\
	\alpha
\end{bmatrix}^T
$

\[ 
\alpha^5 + 1 + \alpha^2 + \alpha^4 + \alpha^6 + \alpha^1 + \alpha^3
=
\begin{array}{c c}
	 & \alpha^5 \\
	 & \alpha^0 \\
	 & \alpha^2 \\
	 & \alpha^4 \\
	 & \alpha^6 \\
	 & \alpha^1 \\
	+ & \alpha^3 \\
	 \hline
	& 0
\end{array}
\Leftrightarrow
\begin{array}{c c c c c c}
	& [ & 1 & 1 & 1 & ] \\
	& [ & 1 & 0 & 0 & ] \\
	& [ & 0 & 0 & 1 & ] \\
	& [ & 0 & 1 & 1 & ] \\
	& [ & 1 & 0 & 1 & ] \\
	& [ & 0 & 1 & 0 & ] \\
	+ & [ & 1 & 1 & 0 & ] \\
	\hline
	& [ & 0 & 0 & 0 & ] \\
	
\end{array}
\]

(zelfde doen voor veelterm: $1 + \alpha + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 = 0$)

$\Rightarrow$ 
$c = 
\begin{bmatrix}
	0 & 0 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
=
\begin{bmatrix}
	0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\
	0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\
	0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0
\end{bmatrix}$



\subsection*{oplossing 1.(e)}
$c * H^T =
\begin{bmatrix}
	0 & 0 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
*
\begin{bmatrix}
	1 & 0 \\
	0 & 1 \\
	1 & 1 \\
	\alpha & 1 \\
	\alpha^2 & 1 \\
	\alpha^3 & 1 \\
	\alpha^4 & 1 \\
	\alpha^5 & 1 \\
	\alpha^6 & 1
\end{bmatrix}^T
=
\begin{bmatrix}
	0 + 0 + \alpha^2 + \alpha^4 + \alpha^6 + \alpha^8 + \alpha^{10} + \alpha^5 + \alpha^7 \\
	0 + 0 + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 + 1 + \alpha
\end{bmatrix}\\
=
\begin{bmatrix}
	0 & 0
\end{bmatrix}
=
\begin{bmatrix}
	0 & 0 \\
	0 & 0 \\
	0 & 0
\end{bmatrix}
$

Dit is een verwachte uitkomst, aangezien er geen fout is toegevoegd moet het resultaat 0 zijn (p.40 cursus).



\subsection*{oplossing 1.(f)}
fout positie 3, grootte $\alpha^2$:\\
$e =
\begin{bmatrix}
	0 & 0 & \alpha^2 & 0 & 0 & 0 & 0 & 0 & 
\end{bmatrix}
$

$
v = c + e =
\begin{bmatrix}
	0 & 0 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
+
\begin{bmatrix}
	0 & 0 & \alpha^2 & 0 & 0 & 0 & 0 & 0 & 
\end{bmatrix}
=
\begin{bmatrix}
	0 & 0 & 0 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
$

$s = v * H^T =
\begin{bmatrix}
	0 & 0 & 0 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
*
\begin{bmatrix}
	1 & 0 \\
	0 & 1 \\
	1 & 1 \\
	\alpha & 1 \\
	\alpha^2 & 1 \\
	\alpha^3 & 1 \\
	\alpha^4 & 1 \\
	\alpha^5 & 1 \\
	\alpha^6 & 1
\end{bmatrix}^T
=
\begin{bmatrix}
	\alpha^4 + \alpha^6 + \alpha^8 + \alpha^{10} + \alpha^5 + \alpha^7 \\
	\alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 + 1 + \alpha
\end{bmatrix}\\
=
\begin{bmatrix}
	\alpha^2 & \alpha^2
\end{bmatrix}
=
\begin{bmatrix}
	0 & 0 \\
	0 & 0 \\
	1 & 1
\end{bmatrix}
$



\subsection*{oplossing 1.(g)}
Hierboven (1.(e)) hebben we het syndroom bepaald:

$
s =
\begin{bmatrix}
	\alpha^2 & \alpha^2
\end{bmatrix}
=
\alpha^2 * 
\begin{bmatrix}
	1 & 1
\end{bmatrix}
$

De vector [1 1] vinden we terug in kolom 3 van $H$. Er is dus een fout van grootte $\alpha^2$ op de 3-e plaats toegevoegd. Dus we kunnen decoderen als volgt:

$e =
\begin{bmatrix}
	0 & 0 & \alpha^2 & 0 & 0 & 0 & 0 & 0 & 
\end{bmatrix}
$

$
c = v - e =
\begin{bmatrix}
	0 & 0 & 0 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
-
\begin{bmatrix}
	0 & 0 & \alpha^2 & 0 & 0 & 0 & 0 & 0 & 
\end{bmatrix}
$\\
$
=
\begin{bmatrix}
	0 & 0 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 & 1 & \alpha
\end{bmatrix}
$













%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 2}
(a) Bepaal de generatorveelterm van een BCH-code van lengte $n = 12$ over $GF(7)$ die $t=2$ fouten kan verbeteren. Kies hierbij $l$ de kleinste waarde in $\mathbb{N}_0$ die de dimensie van de code maximaal maakt.

(b) Decodeer met behulp van het PGZ(=Peterson-Gorenstein-Zierler)-algoritme het ontvangen woord $v(x) = 2x + 5x^2 + 6x^4 + x^4 + 4x^5$.




\subsection*{oplossing 2.(a)}
Generatorveelterm: p.51 cursus.\\
BCH-code: p.28 cursus.

$n= 12, q=7$\\
$n = q^k - 1$ (p.28 cursus)\\
$k=1 \Rightarrow 7^1 - 1 = 6 \neq 12$\\
$k=2 \Rightarrow 7^2 - 1 = 48 \neq 12$\\
$\Rightarrow n \neq q^k - 1 \Rightarrow$ procedure op p.30 gebruiken.

$k$ zo klein mogelijk zodat: $q^k \pmod{12} = 1 \Rightarrow q^k - 1 = n * l$\\
$k=1 \Rightarrow 7^1 \pmod{12} = 7  \neq 1$\\
$k=2 \Rightarrow 7^2 \pmod{12} = 29 \pmod{12} = 1$\\
$\Rightarrow q^k - 1 = n * l \Rightarrow 7^2 - 1 = 12 * 4$\\
$\Rightarrow n=12, q=7, k=2, l=4$

Stel $\beta = \alpha^4$ met $\alpha$ een primitief element van $GF(7^2) = GF(49)$.\\
Neem $\alpha$ het nulpunt van de primitieve veelterm: $x^2 + x + 3$ over $GF(7)$.\\
$\Rightarrow \alpha^2 + \alpha + 3 = 0 \Rightarrow \alpha^2 = - \alpha  - 3 \pmod{7} \Rightarrow \alpha^2 = 6\alpha + 4$

Elementen bepalen:\\
$\beta^{0} = {\alpha^{4}}^0 = \alpha^{0} = 1$\\
$\beta^{1} = {\alpha^{4}}^1 = \alpha^{4} = (6\alpha + 4)^2 = 5\alpha + 6$\\
$\beta^{2} = {\alpha^{4}}^2 = \alpha^{8} = (5\alpha + 6)^2 = 0\alpha + 3 = 3$\\
$\beta^{3} = {\alpha^{4}}^3 = \alpha^{12} = \alpha + 4$\\
$\beta^{4} = {\alpha^{4}}^4 = \alpha^{16} = 2$\\
$\beta^{5} = {\alpha^{4}}^5 = \alpha^{20} = 3\alpha + 5$\\
$\beta^{6} = {\alpha^{4}}^6 = \alpha^{24} = 6$\\
$\beta^{7} = {\alpha^{4}}^7 = \alpha^{28} = 2\alpha + 1$\\
$\beta^{8} = {\alpha^{4}}^8 = \alpha^{32} = 4$\\
$\beta^{9} = {\alpha^{4}}^9 = \alpha^{36} = 6\alpha + 3$\\
$\beta^{10} = {\alpha^{4}}^{10} = \alpha^{40} = 5$\\
$\beta^{11} = {\alpha^{4}}^{11} = \alpha^{44} = 4\alpha + 2$\\
$\beta^{12} = {\alpha^{4}}^{12} = \alpha^{48} =  \beta^0 = 1$



Cyclotomische nevenklassen en minimaalveeltermen voor $\beta$ modulo 12 over $GF(7)$:\\
$C_0 = \{ 0 \} \rightarrow m_0 = (x - \beta^{0}) = (x - 1) = (x + 6)$\\
$C_1 = \{ 1, 7 \} \rightarrow m_1 = (x - \beta^{1})(x - \beta^{7}) = (x^2 + 4)$\\
$C_2 = \{ 2 \} \rightarrow m_2 = (x - \beta^{2}) = (x + 4)$\\
$C_3 = \{ 3,9 \} \rightarrow m_3 = (x - \beta^{3})(x - \beta^{9}) = (x^2 + 1)$\\
$C_4 = \{ 4 \} \rightarrow m_4 = (x - \beta^{4}) = (x + 5)$\\
$C_5 = \{ 5,11 \} \rightarrow m_5 = (x - \beta^{5})(x - \beta^{11}) = (x^2 + 2)$\\
$C_6 = \{ 6 \} \rightarrow m_6 = (x - \beta^{6}) = (x + 1)$\\
$C_8 = \{ 8 \} \rightarrow m_8 = (x - \beta^{8}) = (x + 3)$\\
$C_{10} = \{ 10 \} \rightarrow m_{10} = (x - \beta^{10}) = (x + 2)$


Vervolgens $g(x)$ zoeken zodat $g(\beta^{l}) = g(\beta^{l+1}) = \ldots = g(\beta^{l+2t-1}) = 0$\\
($g(x)$ is een product van minimaalveeltermen (zie vb.57 p.58))\\
Hoe groter $k$, hoe minder redunantie. De graad van $g(x) = n - k$, dus hoe lager de graad van $g(x)$, hoe minder redunantie. Het is de bedoeling om $l$ zo te kiezen, zodat $g(x)$ een zo klein mogelijke graad heeft.



\subsection*{oplossing 2.(b)}
PGZ: p.62 cursus.\\
Algoritme PGZ: p.64.

$v(x) = 2x + 5x^2 + 6x^4 + x^4 + 4x^5$

$\Lambda(x) = 6 + x^2$\\
nulpunten: $x^2 = -6 = 1$\\
$X_1 = 1 = \beta^0 \rightarrow$ fout op positie 1\\
$X_2 = -1 = \beta^6 \rightarrow$ fout op positie 7

foutwaarden: $Y_1 = 1, Y_2 = 5$

foutvector = $e(x) = 1 + 5x^6$\\
codewoord = $c(x) = v(x) - e(x) = 6 + 2x + 5x^2 + 6x^3 + x^4 + 4x^5 + 2x^6$\\
informatiewoord = $i(x) = c(x)/g(x) = 2$\\
$g(x)$ was dus gelijk aan $3+2x+2.5x^2+3x^3+0.5x^4+2x^5+x^6\\ = 3+2x+6x^2+3x^3+4x^4+2x^5+x^6$\\
($2.5 = 5/2 = -2/2 = 6$ en $1/2 = -6/2 = 4$)




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 3}
Beschouw een BCH-code van lengte $n=5$ over $GF(4)$ die $t=1$ fouten kan verbeteren. Kies hierbij $l$ de kleinste waarde in $\mathbb{N}_0$ die e dimensie van de code maximaal maakt. Decodeer het ontvangen woord $v =$ 10 11 11 11 01 met het PGZ algoritme.

$GF(4)$ als uitbreiding van $GF(2)$\\
Primitief element: $\eta$: nulpunt van $x^2 + x + 1$ over $GF(2)$.\\
$\eta^2 + \eta + 1 = 0  \rightarrow  \eta^2 = 1 + \eta$\\
$\eta^0 = 1$\hspace{0.5cm}$\eta^1 = \eta$\hspace{0.5cm}$\eta^2 = 1 + \eta$\hspace{0.5cm}$(\eta^3 = 1)$

$GF(16)$ als uitbreiding van $GF(4)$\\
Primitief element: $\alpha$: nulpunt van $x^2 + \eta x + \eta$ over $GF(4)$.\\
$\alpha^2 + \eta \alpha + \eta = 0   \rightarrow  \alpha^2 = \eta + \eta \alpha$\\
\begin{tabularx}{\textwidth}{XXX}
$\alpha^{0} = 1$

$\alpha^{1} = \alpha$

$\alpha^{2} = \eta + \eta \alpha$

$\alpha^{3} = \eta^2 + \alpha$

$\alpha^{4} = \eta + \alpha$

&

$\alpha^{5} = \eta$

$\alpha^{6} = \eta \alpha$

$\alpha^{7} = \eta^2 + \eta^2 \alpha$

$\alpha^{8} = 1 + \eta \alpha$

$\alpha^{9} = \eta^2 + \eta \alpha$

&

$\alpha^{10} = \eta^2$

$\alpha^{11} = \eta^2 \alpha$

$\alpha^{12} = 1 + \alpha$

$\alpha^{13} = \eta + \eta^2 \alpha$

$\alpha^{14} = 1 + \eta^2 \alpha$

\end{tabularx}




\subsection*{oplossing 3}
$n=5, q=4$\\
$n = q^k - 1$? (methode p.28)\\
$k = 1 \Rightarrow 4^1 - 1 = 3 \neq 5$\\
$k = 2 \Rightarrow 4^2 -1 = 15 \neq 5$\\
$\Rightarrow n \neq q^k - 1 \Rightarrow$ procedure p.30 gebruiken.

Kies $k$ zo klein mogelijk zodat: $q^k \pmod{12} = 1 \Rightarrow q^k - 1 = n * l$\\
$k=1 \Rightarrow 4^1 \pmod{5} = 4  \neq 1$\\
$k=2 \Rightarrow 4^2 \pmod{5} = 1$\\
$\Rightarrow q^k - 1 = n * l \Rightarrow 4^2 - 1 = 5 * 3$\\
$\Rightarrow n=5, q=4, k=2, l=3$ (andere $l$ dan deze uit de opgave)\\
$\Rightarrow \beta = \alpha^3$

Primitief element is al bepaald = $\alpha$: nulpunt van $x^2 + \eta x + \eta$ over $GF(4)$.

Elementen bepalen:\\
$\beta^{0} = {\alpha^{3}}^0 = \alpha^{0} = 1$\\
$\beta^{1} = {\alpha^{3}}^1 = \alpha^{3} = \eta^2 + \alpha$\\
$\beta^{2} = {\alpha^{3}}^2 = \alpha^{6} = \eta \alpha$\\
$\beta^{3} = {\alpha^{3}}^3 = \alpha^{9} = \eta^2 + \eta \alpha$\\
$\beta^{4} = {\alpha^{3}}^4 = \alpha^{12} = 1 + \alpha$\\
$\beta^{5} = {\alpha^{3}}^5 = \alpha^{15} = \alpha^0 = 1$

Bepaal de cyclotomische nevenklassen: (komt overeen met oefenzitting 5 oef 1.b)\\
$C_{\beta,0} = \{ 0 \} \rightarrow m^{(0)}  = (x - \beta^0) = x + 1$\\
$C_{\beta,1} = \{ 1,4 \} \rightarrow m^{(1)}  = (x - \beta^1)(x - \beta^4) = x^2 + \eta x + 1$\\
$C_{\beta,2} = \{ 2,3 \} \rightarrow m^{(2)}  = (x - \beta^2)(x - \beta^3) = x^2 + \eta^2 x + 1$\\
(zie ook oefenzitting 4, oef 3.d, zie voorbeeld 22, p.25 cursus)


De code moet 1 fout kunnen verbeteren $t=1$, dus $2t$ opeenvolgende machten van $\beta$ moeten nulpunten zijn van $g(x)$, dus $g(x)$ moet 2 nulpunten hebben en dus minimaal graad 2 hebben. (p.58)\\
We kiezen hiervoor $l=2$ want $g(\beta^2) = g(\beta^3) = 0$\\
$\Rightarrow g(x) = m^{(2)} = 1 + \eta^2 x + x^2$


Decodeer het ontvangen woord $v =$ 10 11 11 11 01.\\
$\Rightarrow v(x) = 1 + \eta^2 x + \eta^2 x^2 + \eta^2 x^3 + \eta x^4$

Bepalen syndromen: (p.61)\\
$k=1 \Rightarrow S_1 = v(\beta^{2}) = 1 + \eta^3 \alpha + \eta^4 \alpha^2 + \eta^5 \alpha^3 + \eta^5 \alpha^4 =
1 + \eta \alpha = \alpha^8
$\\
$k=2 \Rightarrow S_2 = v(\beta^{3}) = \alpha^2$

Bepalen aantal fouten: (p.64)\\
$t=1 \Rightarrow H^{(1)} = [\alpha^8]$\\
$\Rightarrow det(H^{(1)}) = \alpha^8 \neq 0$\\
$\Rightarrow \upsilon = 1$

Bepalen foutpositie: (p.64, 61)\\
$\Rightarrow [S_1] [\Lambda_0] = [-S_2]$\\
$\Rightarrow \alpha^8 * \Lambda_0 = \alpha^2 \Rightarrow \Lambda_0 = \alpha^2 / \alpha^8 = 1 / \alpha^6 = \alpha^9$\\
$\Lambda(x) = \alpha^9 + x$ met nulpunt $X_1 = \alpha^9 = \beta^3$\\
$\Rightarrow$ fout op positie 4.

Bepalen fout: (p.64)\\
$\Rightarrow [X_1^l] [Y_1] = [S_1]$\\
$\Rightarrow (\alpha^9)^2 * Y_1 = \alpha^8 \Rightarrow Y_1 = \alpha^8 / \alpha^{18} = 1 / \alpha^{10} = \alpha^5$\\
$\Rightarrow Y_1 = \alpha^5 = \eta$ (= grootte fout)

fout:\\
$\Rightarrow e(x) = 
\begin{array}{c c c c c}
	0 & 0 & 0 & \eta & 0
\end{array}
$\\
$\Rightarrow
c(x) = v(x) - e(x) =
\begin{array}{c c c c c}
	1 & \eta^2 & \eta^2 & 1 & \eta
\end{array}
=
\begin{array}{c c c c c}
	10 & 11 & 11 & 10 & 01
\end{array}
$

informatiewoord:\\
$i(x) = c(x)/g(x)=$\\
\[
\begin{array}{c c c c c c | c c c}
	& \eta x^4	& + x^3		& + \eta^2 x^2	& + \eta^2 x	& + 1			& x^2 & + \eta^2 x & + 1 \\ \cline{7-9}
  - & \eta x^4	& + 1x^3	& + \eta x^2	&				&				& \eta x^2 & + 1 \\ \cline{2-4}	
  	& 0			& 0			& x^2 			&              	&				&		 	&\\
  	&			& -			& x^2			& \eta^2 x		& + 1\\ \cline{4-6}
  	&			&			&				&				& 0
\end{array}
\]
$\Rightarrow i(x) =
\begin{array}{c c c}
	1 & 0 & \eta
\end{array}
=
\begin{array}{c c c}
	10 & 00 & 01 
\end{array}
$






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 4}
Beschouw een BCH-code van lengte $n=15$ over $GF(4)$ die $t=4$ fouten kan verbeteren. Neem $l=1$. Decodeer het ontvangen woord $v(x) = x^2 + \eta x^5 + \eta^2 x^{13}$ (met $\eta^2 + \eta + 1 = 0$ (zie hoger)) met het PGZ algoritme.


\subsection*{oplossing 4}
$n=15, q=4$\\
$n = q^k - 1$? (methode p.28)\\
$k = 1 \Rightarrow 4^1 - 1 = 3 \neq 5$\\
$k = 2 \Rightarrow 4^2 - 1 = 15 = n$

Construeer het uitbreidingsveld $GF(4^2) = GF(16)$ van $GF(4)$ en neem een primitief element $\alpha \in GF(16)$, $\beta = \alpha$ (p.28, puntje 1 en 2):\\
Primitief element: $\alpha$: nulpunt van $x^2 + \eta x + \eta$ over $GF(4)$.\\
$\alpha^2 + \eta \alpha + \eta = 0   \rightarrow  \alpha^2 = \eta + \eta \alpha$\\
(Zie opgave 3 hierboven)

Bepaal de cyclotomische nevenklassen modulo $n = 4^2 -1 = 15$ over $GF(4)$, en bepaal voor elke nevenklasse de minimaalveelterm. (p.28, puntje 3 en 4):\\
$C_{0} = \{ 0 \} \rightarrow m^{(0)}  = (x - \alpha^{0}) = x + 1$\\
$C_{1} = \{ 1, 4 \} \rightarrow m^{(1)}  = (x - \alpha^{1})(x - \alpha^{4}) = x^2 + \eta x + \eta$\\
$C_{2} = \{ 2, 8 \} \rightarrow m^{(2)}  = (x - \alpha^{2})(x - \alpha^{8}) = x^2 + \eta^2 x + \eta$\\
$C_{3} = \{ 3, 12 \} \rightarrow m^{(3)}  = (x - \alpha^{3})(x - \alpha^{12}) = x^2 + \eta x + 1$\\
$C_{5} = \{ 5 \} \rightarrow m^{(5)}  = (x - \alpha^{5}) = x + \eta$\\
$C_{6} = \{ 6, 9 \} \rightarrow m^{(6)}  = (x - \alpha^{6})(x - \alpha^{9}) = x^2 + \eta^2 x + 1$\\
$C_{7} = \{ 7, 13 \} \rightarrow m^{(7)}  = (x - \alpha^{7})(x - \alpha^{13}) = x^2 + x + \eta$\\
$C_{10} = \{ 10 \} \rightarrow m^{(10)}  = (x - \alpha^{10}) = x + \eta^2$\\
$C_{11} = \{ 11, 14 \} \rightarrow m^{(11)}  = (x - \alpha^{11})(x - \alpha^{14}) = x^2 + x + \eta^2$\\
(zie ook oefenzitting 4, oef 3.d, zie voorbeeld 22, p.25 cursus)


De code moet $t=4$ fouten kunnen verbeteren, dus $2t$ opeenvolgende machten van $\beta$ moeten nulpunten zijn van $g(x)$, dus $g(x)$ moet 8 nulpunten hebben en dus minimaal graad 8 hebben (p.58). Als $l$ nemen we $l=1$.\\
\[
g(x) = (x - \beta^{1})(x - \beta^{2})(x - \beta^{3})(x - \beta^{4})(x - \beta^{5})(x - \beta^{6})(x - \beta^{7})(x - \beta^{8})
\]
\[
= m^{(1)} * m^{(2)} * m^{(3)} * m^{(5)} * m^{(6)} * m^{(7)}
\]
\[
= (x^2 + \eta x + \eta) (x^2 + \eta^2 x + \eta) (x^2 + \eta x + 1) (x + \eta) (x^2 + \eta^2 x + 1) (x^2 + x + \eta)
\]
\[
= \text{niet berekend wegens teveel werk}
\]


Ontvangen woord: $v(x) = x^2 + \eta x^5 + \eta^2 x^{13}$.\\
Hieruit kunnen we de syndromen berekenen volgens p.61:\\
\[
\begin{array}{c | c c c c c c c c c}
	k 	& 1		& 2 		& 3 			& 4 	& 5 			& 6 		& 7 		& 8 \\
	\hline
	S_k & 0		& \alpha^7 	& \alpha^{11}	& 0		& \alpha^{10}	& \alpha^8	& \alpha^5 	& \alpha^{13}
\end{array}
\]



Vervolgens gaan we $v(x) = x^2 + \eta x^5 + \eta^2 x^{13}$ proberen te decoderen m.b.v. het PGZ algoritme op p.64.\\
(Aangezien dit veel te veel rekenwerk is (determinanten van $4 \times 4$ matrices enzo), gaat hieronder alleen maar de uitkomst te vinden zijn ;-) )

$\upsilon = 3$: 3 fouten

$\Lambda(x) = \alpha^5 + \alpha^8 x + \alpha^4 x^2 + x^3$ met nulpunt $X_1 = \beta^2$, $X_2 = \beta^5$, $X_3 = \beta^{13}$.

$Y_1 = 1$, $Y_2 = \alpha^5 = \eta$, $Y_3 = \alpha^{10} = \eta^2$.

$e(x) = x^2 + \eta x^5 + \eta^2 x^{13}$, $c(x) = v(x) - e(x) = 0, i(x) = 0$.





\end{document}
